class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int ans = 0;
        int begin = 0;
        if(prices.size() < 2) {
            return ans;
        }
        int end = 1;
        int n = prices.size();
        while(begin < n - 1 && prices[begin] >= prices[begin + 1]) {
            ++begin;
        }
        if(begin >= n - 1) {
            return ans;
        }
        end = begin + 1;
        while(true) {
            while(end < n && prices[end] >= prices[end - 1]) {
                ++end;
            }
            if(prices[end - 1] - prices[begin] > ans) {
                ans = prices[end - 1] - prices[begin];
            }
            if(end == n) {
                break;
            }
            if(prices[end] < prices[begin]) {
                begin = end;
            }
            ++end;
        }
        return ans;
    }
};